package utils;

import java.util.Arrays;

/**
 * 堆排序工具类
 * 堆排序在所有情况下的时间复杂度多是 O(n log n)
 */
public class HeapSort {
    //堆排序，这里用大根堆，即所有的父节点都比其所有的子节点大
    public static void heapSort(int[] arr){
        int n = arr.length;
        //调整每个非叶子节点，从而变成大根堆
        for(int i=n/2-1;i>=0;i--){
            heapify(arr,n,i);
        }
        //遍历，每次都将顶点也就是当前排序序列中的最大值放到当前序列的最后，从而排成从小到大的顺序
        for(int i=n-1;i>=0;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //交换顺序后继续调整堆
            heapify(arr,i,0);
        }
    }

    //调整堆，调整某个节点的子树
    public static void heapify(int[] arr,int n,int i){
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //左孩子存在，且左孩子的数值大于当前指向节点（即父节点）
        if(left < n && arr[left] > arr[largest]){
            largest = left;
        }
        //右孩子存在，且右孩子的数值大于当前指向节点（如果上个条件不满足，这里就是父节点，如果满足就是左孩子）
        if(right < n && arr[right] > arr[largest]){
            largest = right;
        }

        //如果父节点不是最大值
        if(i != largest){
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            //largest是交换过的节点，要校验并调整这个节点的子树
            heapify(arr,n,largest);
        }
    }

    public static void main(String[] args) {
        int[] array1 = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前数组: " + Arrays.toString(array1));
        heapSort(array1);
        System.out.println("排序后数组: " + Arrays.toString(array1));

        int[] array2 = {4, 10, 3, 5, 1};
        System.out.println("排序前数组: " + Arrays.toString(array2));
        heapSort(array2);
        System.out.println("排序后数组: " + Arrays.toString(array2));

        int[] array3 = {1, 3, 20, 29, 5, 7, 31, 0, 33, 9};
        System.out.println("排序前数组: " + Arrays.toString(array3));
        heapSort(array3);
        System.out.println("排序后数组: " + Arrays.toString(array3));
    }
}
